Title: Rounding Techniques in Approximation Algorithms

Q: Definition of Approximation Algorithm
A: An \(\alpha\)-approximation for an optimization problem is a polynomial time algorithm which produces a solution of cost within a factor of \(\alpha\) of the optimal solution for every instance.

Q: Integer Linear Program and Linear Program Relaxation
A: An Integer Linear Program (ILP) minimizes a linear objective function over a convex polyhedron \(P\). The variables are constrained to be integers. \[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{Z}_{\ge 0}^n
\end{align*}\]If we instead only constrain the variables to be real numbers, we get a Linear Program (LP):\[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{R}_{\ge 0}^n
\end{align*}\]Note we can flip min to max by negating the entries of \(c\), so these programs are fully general.

Q: Integrality Gap
A: The integrality gap of an ILP and its associated LP is the worst case ratio between the ILP OPT and the LP OPT over all instances.

Q: Ellipsoid method and separation oracle
A: Let \(P\) be a convex set. A separation oracle for \(P\) is a polynomial time procedure that given a point \(x \in \mathbb{R}^n\), either certifies that \(x \in P\) or returns a hyperplane that separates \(x\) from \(P\). In other words, it returns a a vector \(a \in \mathbb{R}^n\) such that \(a^Tx > a^Ty\) for all \(y \in P\).
The ellipsoid method is a polynomial time algorithm that can optimize over any convex set with a separation oracle. (In other words, it can solve any LP whose feasible region is convex and has a separation oracle.)
In this course, \(P\) will typically be a convex polyhedron defined by a (possibly exponential size) collection of hyperplanes, and our separation oracle will return one of these hyperplanes.

Q: Relax and round framework
A: Start with an ILP with a separation oracle whose feasible solutions are the feasible solutions for your optimization problem. Then, relax it to an LP, which is polynomial time solvable by the ellipsoid method. After solving this LP, round the resulting solution to a feasible integer solution.

Q: Polyhedron and polytope
A: A polyhedron is the intersection of a finite number of halfspaces. A polytope is a bounded polyhedron.

Q: Threshold rounding
A: The simplest kind of LP rounding. Given an LP solution, round all variables above a certain threshold to their ceiling.
This works for "covering" problems like Vertex Cover in which the constraints are of the form \(a^Tx \ge b\) for \(a \in \mathbb{R}_{\ge 0}^n, b \in \mathbb{R}\).

Q: Union Bound
A: Given \(n\) events \(B_1,\dots,B_n\), the probability any of the events \(B_i\) occur is at most \(\sum_{i=1}^n \mathbb{P}[B_i]\).
In its typical usage, we want to avoid all of the events \(B_i\) with some probability. The union bound says that with probability at least \(1-\sum_{i=1}^n \mathbb{P}[B_i]\), none of the events occur.

Q: Chernoff Bound Lower Tail
A: Let \(X_1,\dots,X_n\) be independent Bernoulli random variables. Then if \(X = \sum_{i=1}^n X_i\), \(L \le \mathbb{E}[X]\), and \(0 \le \delta \le 1\), we have:\[\mathbb{P}[X \le (1-\delta)L] \le \exp(-L\delta^2/2)\]

Q: Chernoff Bound Upper Tails
A: Let \(X_1,\dots,X_n\) be independent Bernoulli random variables. Let \(X = \sum_{i=1}^n X_i\), \(\mathbb{E}[X] \le U\). For small \(\delta >0\), one can use\[\mathbb{P}[X \ge (1+\delta)U] \le \exp(-U\delta^2/(2+\delta))\]When \(\delta \le 1\), often you will see \(\exp(-U\delta^2/3)\). For large \(\delta \ge 2\), the following is stronger: \[\mathbb{P}[X \ge (1+\delta)U] \le \exp(-U\delta \ln \delta/4)\]If you prefer to just remember one bound that can be used to obtain both of these, you can use this for all \(\delta > 0\):\[\mathbb{P}[X \ge (1+\delta)U] < \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^U\]In practice it is just slightly more cumbersome to use. On the quiz, either remember the two bounds for differing values of delta or remember the last bound.

Q: Independent Randomized Rounding
A: In independent randomized rounding, we treat a variable \(x_i\) as a probability. Typically, we will have each \(x_i \in [0,1]\) and we round each variable independently \(i\) to 1 with probability \(x_i\).
This method is used in a straightforward manner for Set Cover (Homework 1) and Karger's argument for \(k\)-edge-connectivity. For the min-congestion multi-commodity flow problem, we treat the paths for each commodity as an independent distribution, but (in a slight twist of this framework) ensure we pick exactly one path. This allows us to ensure we get a feasible solution with probability 1 but still apply Chernoff / Union bounds.

Q: Definition of a vertex of a polyhedron and of an extreme point solution
A: A  vertex of a polyhedron \(P\) is a point \(x\) for which these exists no non-zero direction \(d\) such that \(x+d \in P\) and \(x-d \in P\).
Given an LP over a polyhedron \(P\), an extreme point solution is a vertex of \(P\). As long as the optimal solution to this LP is bounded, there is guaranteed to be an optimal solution which is a vertex. This can be proved using Carathéodory's theorem.

Q: Carathéodory's Theorem
A: If \(x \in \mathbb{R}^n\) is a point in a polytope \(P\), then we can write \(x\) as a convex combination of at most \(n+1\) vertices \(v_1,\dots,v_{n+1}\) of \(P\).
In other words, we have \(x = \sum_{i=1}^{n+1} \lambda_i v_i\) where \(\sum_{i=1}^n \lambda_i = 1\) and \(\lambda_i \ge 0\) for all \(i\).

Q: An inequality for \(e\)
A: \(1-x \le e^{-x}\) for all \(x \in \mathbb{R}\), positive or negative
In general remember \(e^x = 1+x+x^2/2!+x^3/3!+\dots\) by Maclaurin series. So for small \(|x|\), we have \(e^x \approx 1+x\).

Q: 4-color theorem
A: The vertices of a planar graph can be 4-colored. Furthermore, this can be done in polynomial time.

Q: Asymptotics of \(H_n\), the Harmonic Series
A: \(H_n = \sum_{k=1}^n \frac{1}{k}\). As \(n \to \infty\), we have \(H_n = (1+o(1))\ln(n)\).

Q: \(\alpha\)-near minimum cuts and Karger's bound on their number
A: Given a \(k\)-edge-connected graph, a cut is \(\alpha\)-near minimum if it has at most \(\alpha k\) edges. Karger's bound shows there are at most \(n^{2\alpha}\) \(\alpha\)-near minimum cuts.

Q: Nash Williams Theorem
A: Every \(k\)-edge-connected graph contains \(k/2\) edge disjoint spanning trees.